﻿#include"heap.h"

void HpInit(Hp* hp, Datatype* b, int n)  //对使用传入的数组首元素地址和数组长度对堆中数组进行初始化（非原地）
{
	assert(hp);
	assert(hp->a);

	hp->capacity = 2*n;
	hp->size = 0;
	
	Datatype* tmp = (Datatype*)malloc(sizeof(Datatype) * 2 * n);
	if (tmp==NULL)
	{
		perror("malloc falil");
	}
	hp->a = tmp;

	for (int i = 0; i < n; i++)
	{
		HpPush(hp, b[i]);
	}
}

void HpInitUp(Hp* hp, Datatype* f, int Datasize)  //在原地向上建堆初始化
{
	hp->a = f;
	hp->size = 0;
	hp->capacity = Datasize;

	for (int i = 0; i < Datasize; i++)
	{
		HpPush(hp, f[i]);
	}
}

void HPInitDown(Datatype* z,int zsize)  //原地向下建堆（传入的数组已经有了数据）
{
	for (int i = (zsize-2)/2; i >= 0; i--)
	{
		DelHpDown(z, zsize, i);
	}
	HpPrintf(z, zsize);
}

void swap(Datatype* d, Datatype* e)  //交换d和e指向的变量的值
{
	Datatype tmp;

	tmp = *d;
	*d = *e;
	*e = tmp;
}

void AddHpUp(Datatype* a, int n, int child)  //向上调整函数：a为传入数组首元素，n为数组目前数据数量，child为需要向上调整的数据的下标
{
	//思路：1.找到父节点 2.比较父节点与子节点 2.选出较小数进行值交换 3.child=parent,将需要继续向上调整的父节点的小标给child，进行循环 4.循环继续的条件为child!=0

	while (child!=0)
	{
		int parent = (child - 1) / 2;
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
		}
		else
		{
			break;
		}
	}
}

void HpPush(Hp* hp, Datatype c)  //把数据c加入到堆中
{
	assert(hp);

	if (hp->size+1>hp->capacity)
	{
		printf("堆已满，无法再添加数据！\n");
	}
	else
	{
		hp->a[hp->size] = c;
		hp->size++;

		AddHpUp(hp->a, hp->size, hp->size - 1);
	}
}

void DelHpDown(Datatype* a, int size, int parent)  //向下调整函数：a为传入数组首元素地址，size为数组目前数据个数，parent为需要向下调整的数据的下标
{
	//思路：1.定义一个child变量存放该父节点对应的子节点下标（初始值默认为leftchild） 2.将a[child]与a[child+1]（在child+1没有出界的情况）进行比较，若a[child+1]小则child++；否则不动
	//      3.判断a[child]与a[parent]的值大小
	
	int child = parent * 2 + 1;

	while (child<=size - 1)
	{
		if (a[child+1]<a[child]&&child+1<=size-1)   //看右节点是否也小于父节点，并且存在右节点
		{
			child++;
		}
		if (a[child]<a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}	
}

//反思：这里不用左右节点变量能减少好多问题，而且对一个内部有逻辑的结构，不能轻易交换元素位置，写这种操作需要想想会有哪些后果，边界值判断非常重要

void HpPop(Hp* hp)  //把根元素从堆中删除
{
	//思路：1.将根元素与尾部元素交换 2.处理size 3.将新的根元素向下调整
	swap(&hp->a[0], &hp->a[hp->size - 1]);

	hp->size--;

	DelHpDown(hp->a, hp->size, 0);
	
}

void HpPrintf(Datatype* a, int size)  //打印堆中的所有数据
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void HpSort(Datatype* a, int size)  //使用堆对传入的数组a进行原地建堆排序
{
	Hp hp;
	//思路：1.原地建堆（升序建大堆） 2.循环：每次pop出堆内最大值到数组尾（直到size=1）
	HpInitUp(&hp, a, size);

	for (int i = 0; i < size; i++)
	{
		HpPop(&hp);
	}
}

//TopK问题：当数据量巨大，且无法在内存中一次性存储，需要存在硬件的文件里，要找出该数据中前k个数时

void CreateData()  //创建一个文件并且随即生成十万以内的10000个数字
{
	int n = 100;
	srand(time(0));
	const char* file = "Data.txt";
	FILE* fin = fopen(file, "w");
	if (fin==NULL)
	{
		perror("fopen fail");
	}
	for (int i = 0; i < n; i++)
	{
		int x = rand() % 10000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

void TopK(int k)     //建堆找出的前k个数字并输出
{
	//思路：1.取文件中的数据 2.先取前k个建堆---创建一个数组，长度为k，导入前k个数据，向下调整建堆  3.依次取文件中的数据与堆的根元素进行比较，比较成功则push进堆，直到文件内数据取完  3.打印堆
	const char* file = "Data.txt";
	FILE* fout = fopen(file, "r");

	Datatype* a = (Datatype*)malloc(sizeof(Datatype) * k);

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d",&a[i]);
	}
	HpPrintf(a,k);
	HPInitDown(a, k);
	int x = 0;
	while (fscanf(fout,"%d",&x)!=EOF)
	{
		if (a[0]<x)
		{
			a[0]=x;
			DelHpDown(a, k, 0);
		}
	}
	HpPrintf(a, k);
}